let tree = [
  {
    id: '1',
    children: [
      {
        id: '1-1',
        children: [
          {
            id: '1-1-1',
          },
          {
            id: '1-1-2',
          },
        ],
      },
      {
        id: '1-2',
        children: [
          {
            id: '1-2-1',
          },
          {
            id: '1-2-2',
          },
        ],
      },
    ],
  },
  {
    id: '2',
    children: [
      {
        id: '2-1',
        children: [
          {
            id: '2-1-1',
          },
          {
            id: '2-1-2',
          },
        ],
      },
      {
        id: '2-2',
        children: [
          {
            id: '2-2-1',
          },
        ],
      },
    ],
  },
  {
    id: '3',
    children: [
      {
        id: '3-1',
        children: [
          {
            id: '3-1-1',
          },
        ],
      },
      {
        id: '3-2',
        children: [
          {
            id: '3-2-1',
          },
        ],
      },
      {
        id: '3-3',
        children: [
          {
            id: '3-3-1',
          },
        ],
      },
    ],
  },
]
// 深度优先遍历
function dfs (tree, rst = []) {
  // 基于栈实现 栈后进先出
  let stack = [...tree]
  while (stack.length) {
    let node = stack.shift()
    rst.push(node.id)
    if (node.children) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.unshift(node.children[i])
      }
    }
  }
  return rst
}
function dfs2 (tree, rst = []) {
  // 使用递归 实现深度优先遍历
  for (let i = 0; i < tree.length; i++) {
    let node = tree[i]
    rst.push(node.id)
    if (node.children) {
      dfs2(node.children, rst)
    }
  }
  return rst
}
// console.log(dfs(tree));
console.log(dfs2(tree));
// // 广度优先遍历
// function bfs (tree, rst = []) {
//   let queue = [...tree] // 基于队列实现 队列先进先出
//   while (queue.length) {
//     // 取出队头元素
//     let qVal = queue.shift()
//     rst.push(qVal.id)
//     if (qVal.children) {
//       qVal.children.forEach(node => {
//         queue.push(node)
//       })
//     }
//   }
//   return rst
// }
// console.log(bfs(tree));
